Search for: All records

Multiplicity code decoders are based on Hermite polynomial interpolation with error correction. In order to have a unique Hermite interpolant one assumes that the field of scalars has characteristic 0 or >= k+1, where k is the maximum order of the derivatives in the list of values of the polynomial and its derivatives which are interpolated. For scalar fields of characteristic k+1, the minimum number of values for interpolating a polynomial of degree <= D is D+1+2E(k+1) when <= E of the values are erroneous. Here we give an error-correcting Hermite interpolation algorithm that can tolerate more errors, assuming that the characteristic of the scalar field is either 0 or >= D+1. Our algorithm requires (k+1)D + 1 - (k+1)k/2 + 2E values. As an example, we consider k = 2. If the error ratio (number of errors)/(number of evaluations) <= 0.16, our new algorithm requires ceiling( (4+7/17) D - (1+8 /17) ) values, while multiplicity decoding requires 25D+25 values. If the error ratio is <= 0.2, our algorithm requires 5D-2 evaluations over characteristic 0 or >= D+1, while multiplicity decoding for an error ratio 0.2 over fields of characteristic 3 is not possible for D >= 3. Our algorithm is based on Reed-Solomon interpolation without multiplicities, which becomes possible for Hermite interpolation because of the high redundancy necessary for error-correction. 

We generalize Hermite interpolation with error correction, which is the methodology for multiplicity algebraic error correction codes, to Hermite interpolation of a rational function over a field K from function and function derivative values. We present an interpolation algorithm that can locate and correct <= E errors at distinct arguments y in K where at least one of the values or values of a derivative is incorrect. The upper bound E for the number of such y is input. Our algorithm sufficiently oversamples the rational function to guarantee a unique interpolant. We sample (f/g)^(j)(y[i]) for 0 <= j <= L[i], 1 <= i <= n, y[i] distinct, where (f/g)^(j) is the j-th derivative of the rational function f/g, f, g in K[x], GCD(f,g)=1, g <= 0, and where N = (L[1]+1)+...+(L[n]+1) >= C + D + 1 + 2(L[1]+1) + ... + 2(L[E]+1) where C is an upper bound for deg(f) and D an upper bound for deg(g), which are input to our algorithm. The arguments y[i] can be poles, which is truly or falsely indicated by a function value infinity with the corresponding L[i]=0. Our results remain valid for fields K of characteristic >= 1 + max L[i]. Our algorithm has the same asymptotic arithmetic complexity as that for classical Hermite interpolation, namely soft-O(N). For polynomials, that is, g=1, and a uniform derivative profile L[1] = ... = L[n], our algorithm specializes to the univariate multiplicity code decoder that is based on the 1986 Welch-Berlekamp algorithm.